package pers.tz.题目;

import static pers.tz.common.ArrayUtils.*;

/**
 * @author irony
 * @date 2024-03-09
 */
public class 二分查找 {
    public static void main(String[] args) {
        int[] ints = generateRandomArray(10, true, 1, 20);
        printArray(ints);

        int index = binarySearch(ints, 5);
        System.out.println("index = " + index);
    }

    /**
     * 二分查找
     *
     * @param arr    有序数组
     * @param target 查找值
     * @return 目标数组索引
     */
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length;

        while (left < right) {
            int middle = (left + right) / 2;
//            int middle = (left + right) >>> 1;
            if (arr[middle] > target) {
                right = middle - 1;
            }

            if (arr[middle] < target) {
                left = middle + 1;
            }

            if (arr[middle] == target) {
                return middle;
            }
        }

        return -1;
    }


}
